﻿<%@ Page Language="C#" AutoEventWireup="true" CodeFile="LCS算法最大公共子串.aspx.cs" Inherits="数据算法_LCS算法" %>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
<head runat="server">
    <title>LCS算法最大公共子串,它是求两个字符串最长公共子串</title>
</head>
<body>
    <form id="form1" runat="server">
    <asp:Label ID="tt" runat="server" Text="Label"></asp:Label>
    
    <div>
    
        <p>
            LCS(<font size="2">longest common substring</font>)算法,即最大公共子串,它是求两个字符串最长公共子串的问题。大体解法是用<font 
                color="#ff0000">一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1，否则为0。然后求出对角线最长的1序列，其对应的位置就是最长匹配子串的位置.</font></p>
        <p>
&nbsp; 例如,有两个字符串:</p>
        <p>
&nbsp; A= I MISS MY CODE HI</p>
        <p>
&nbsp; B= One Like MY&nbsp;Code</p>
        <p>
        </p>
        <p>
&nbsp; 这里,先忽略掉大小写,通吃,在C#或者PHP中,String.ToLower()或者lower()可以考虑.对于其中的特殊字符,例如空格,可以在比较的时候直接删除.另外,该算法比较与顺序无关,<em>可以随意的翻转字符串</em>.接下来比较.</p>
        <p>
            <table align="center" border="0" cellpadding="3" cellspacing="1" 
                style="BORDER-RIGHT: #f00 2px solid; BORDER-TOP: #f00 2px solid; BORDER-LEFT: #f00 2px solid; WIDTH: 360px; BORDER-BOTTOM: #f00 2px solid; BACKGROUND-COLOR: #a2a2a2">
                <tr>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                    </td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        i</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        m</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        i</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        s</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        s</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        m</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        y</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        c</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        o</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        d</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        e</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        h</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        i</td>
                </tr>
                <tr>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        o</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        <font color="red">1</font></td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                </tr>
                <tr>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        n</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                </tr>
                <tr>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        e</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        <font color="red">1</font></td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                </tr>
                <tr>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        l</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                </tr>
                <tr>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        i</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        <font color="red">1</font></td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        <font color="red">1</font></td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        <font color="red">1</font></td>
                </tr>
                <tr>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        k</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                </tr>
                <tr>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        e</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        <font color="red">1</font></td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                </tr>
                <tr>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        m</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        <font color="red">1</font></td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        <font color="red">1</font></td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                </tr>
                <tr>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        y</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        <font color="red">1</font></td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                </tr>
                <tr>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        c</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        <font color="red">1</font></td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                </tr>
                <tr>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        o</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        <font color="red">1</font></td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                </tr>
                <tr>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        d</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        <font color="red">1</font></td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                </tr>
                <tr>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        e</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        <font color="red">1</font></td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                    <td align="middle" style="BACKGROUND-COLOR: #fff">
                        0</td>
                </tr>
            </table>
        </p>
        <p>
&nbsp;&nbsp; 在上面的矩阵图中,其中的红色就可以看成匹配的字符串.<br />
&nbsp;&nbsp; 以下C#代码:<br />
            //Run By LCS.</p>
        <p>
            public string<font color="#ff0000"><strong> </strong></font><em>
            <font color="#ffffff"><font color="#ff0000"><strong>GetSameString</strong></font>
            </font></em>(string ArgA,string ArgB){<br />
            &nbsp;if(String.IsNullOrEmpty(ArgA) || String.IsNullOrEmpty(ArgB)) return 
            String.Empty;<br />
            &nbsp;int[] CompareArr=new int[ArgB.Length];<br />
            &nbsp;int max=0,maxJ=0;<br />
            &nbsp;for(int iloop=0;iloop&lt;ArgA.Length;iloop++){<br />
            &nbsp;&nbsp;for(int jloop=ArgB.Length-1;jloop&gt;=0;jloop--){<br />
            &nbsp;&nbsp;&nbsp;CompareArr[jloop]=(ArgB[jloop]==ArgA[iloop])?( 
            (iloop==0||jloop==0)?1:CompareArr[jloop-1]+1):0;<br />
            &nbsp;&nbsp;&nbsp;if(CompareArr[jloop]&gt;=max){<br />
            &nbsp;&nbsp;&nbsp;&nbsp;max=CompareArr[jloop];<br />
            &nbsp;&nbsp;&nbsp;&nbsp;maxJ=jloop;<br />
            &nbsp;&nbsp;&nbsp;}<br />
            &nbsp;&nbsp;}<br />
            &nbsp;}<br />
            &nbsp;if(max&gt;0){<br />
            &nbsp;&nbsp;return ArgB.Substring(maxJ-max+1,max);<br />
            &nbsp;}else return String.Empty;<br />
            }</p>
        <p>
&nbsp; 注释:如果翻转后(可不翻转)相同,当前数组Index=N的值是N-1的值 + 1,这样,当最长的那条线上的就是最大的数字,同时,记录索引号.这样:</p>
        <p>
&nbsp; Max 就是最多的匹配数,<br />
&nbsp; maxJ就是B字符串的索引.</p>
        <p>
            亦可以这样理解:<br />
&nbsp; 竖的是A字符串,横的是B字符串,为了能在数组中记录上次的比较值,对单行进行倒循环,如果取值相同,该值是<font color="#ff0000"><strong>左上角的值加一</strong></font><font 
                color="#000000">,就是最长的字符串个数,即Max,同时记录当前的B字符串最后相同的索引值.然后用Substring()函数截取即可.</font></p>
        <p>
            5do8&nbsp; Edit&nbsp; At&nbsp; GetLocalDate()</p>
    
    </div>
    </form>
</body>
</html>
